package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 * 使用ArrayList
 *
 * @author fy
 * @date 2022/4/13 9:13
 */
public class Solution380_1 {

    public class RandomizedSet {
        List<Long> list;

        public RandomizedSet() {
            list = new ArrayList<>();
            list.add((long) (-1e15));
            list.add((long) 1e15);
        }

        public boolean insert(int val) {
            int l = 1;
            int r = list.size() - 1;
            while (l < r) {
                int mid = (l + r) / 2;
                if (list.get(mid) <= val) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
                if (l == r - 1) {
                    if (list.get(l) > val) {
                        r = l;
                    }
                    break;
                }
            }
            if (list.get(r - 1) - val == 0) {
                return false;
            }
            list.add(r, (long) val);
            return true;
        }

        public boolean remove(int val) {
            int l = 1;
            int r = list.size() - 1;
            while (l < r) {
                int mid = (l + r) / 2;
                if (list.get(mid) <= val) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
                if (l == r - 1) {
                    if (list.get(l) > val) {
                        r = l;
                    }
                    break;
                }
            }
            if (list.get(r - 1) - val != 0) {
                return false;
            }
            list.remove(r - 1);
            return true;
        }

        public int getRandom() {
            long a = list.get((int) (Math.random() * (list.size() - 2)) + 1);
            return (int) a;
        }
    }


}
